package com.tgy.algorithm.base._递归;

public class _N皇后问题02 {

    public static void printBit(long num,int bit) {

        for (long i = bit - 1; i >= 0; i--) {
            String val = (num & (1 << i)) == 0 ? "0" : "1";
            System.out.print(val);
        }
        System.out.println("");
    }

    public static int getLastOne(int num) {

        // 0010100
        // 1101011
        //   1101100
        // & 0010100

        while (num > 0) {

            int val = num & (~num + 1);
            printBit(val,Integer.SIZE);
            num = num ^ val;
        }
        return 0;
    }

    public static int queen(int num) {

        int all = num == 32 ? -1:((1 << num) - 1);
        printBit(all,Integer.SIZE);
        return doQueen(all,0,0,0);
    }

    public static int doQueen(int all,int vertical,int leftSkew, int rightSkew) {
        if (all == vertical) {
            return 1;
        }

        // 0111;
        int rest = all & (~(vertical | leftSkew | rightSkew));
        int result = 0;
        while (rest > 0) {
            int lastRight = rest & (~rest +1);
            result += doQueen(all,vertical | lastRight,(leftSkew | lastRight) << 1, (rightSkew | lastRight) >>> 1);
            rest = rest ^ lastRight;
        }

        return result;
    }


    public static void main(String[] args) {


//        getLastOne(100);
//        int val = 15;
//        int lastOne = getLastOne(val);
        // 1100
        // 0100
//        printBit(val,Integer.SIZE);
//        printBit(lastOne,Integer.SIZE);
        int queen = queen(8);
        System.out.println(queen);
    }
}
